This application relates to the digital image processing arts. More particularly, the application relates to a method and apparatus for digital image reduction in an efficient and cost-effective manner, with good suppression of moire and other undesirable artifacts as often become more pronounced in a downsampled image such as a reduced-size digital image. Such undesirable moire has been found to be especially severe upon reduction of a scanned halftone image.
Digital image reduction is essentially a down-sampling process whereby image pixel data for a bitmap of n rows.times.m columns is used to construct a smaller bitmap of k rows.times.l columns, where k.ltoreq.n and/or l.ltoreq.m. Of course, while the location of each pixel in the new, reduced-size bitmap is known, its "gray" value is unknown and must be determined with reference to the original image.
Many methods are known for determining the gray value of each pixel in the reduced image. A relatively simple method is commonly referred to as "nearest neighbor" interpolation. In such case, if the reduced-size bitmap is viewed as being superimposed over the original image bitmap, the gray value for each new pixel is simply the value of the spatially closest pixel in the original bitmap. Although fast, nearest neighbor interpolation is often not satisfactory in terms of the quality of the resulting reduced-size image.
Another common interpolation technique used in digital image downsampling is bilinear interpolation. Using bilinear interpolation, the newly generated pixel gray value is set to be the weighted sum of the four nearest original pixels. The weights are determined linearly--i.e., each weight is inversely proportional to the distance from each original pixel. Bilinear interpolation has been found to yield higher quality reduced-size images relative to nearest neighbor interpolation. Of course, bilinear interpolation also requires significantly more computational effort compared to nearest neighbor interpolation. Additionally, bilinear interpolation still often results in severe moire and other undesirable artifacts in the new image.
Techniques have been proposed and implemented for reducing moire which becomes apparent due to downsampling. One prior method involves the application of a two-dimensional low-pass filter to the pixel data of the original image prior to the downsampling operation. The low-pass filter has the effect of reducing high-frequency content in the original image--i.e., the filter has the effect of somewhat "blurring" the original image. This filtered image data is then used in the scaling operation and results in a reduced-size image with less severe moire. Unfortunately, the circuitry required to apply a useful two-dimensional filter to the original image data is expensive to implement. In particular, a relatively large number of scanline buffers are needed to store pixel data from multiple scanlines of the original image. For example, in order to apply a 5.times.5 filter, at least four scanline buffers would typically be needed for the incoming original image data. These scanline buffers add significant expense to the reduction apparatus. Furthermore, reduction of color digital images requires this circuitry to buffer the original image data for each color separation of the original image.
Another prior technique used to reduce moire resulting from downsampling is sometimes referred to as "perspective projection." Perspective projection creates a new pixel from the original image data by averaging a correspondingly located area of the original image. While perspective projection has also been found to be generally effective in reducing moire, in certain cases, such as in the downsampling of halftone image data, moire is still apparent in the resulting image.
Moire apparent after downsampling using perspective projection reduction has resulted from the fact that, heretofore, perspective projection has been implemented so that the size of the area of the original image that is averaged is a linear function of the image reduction ratio. The reduction ratio is defined as 1/scale, where scale=a scaling factor such as 0.5 (a reduction to 50% original size), 0.8 (a reduction to 80% original size), etc. For example, in reducing an image to 50% of original size, a reduction ratio of 2 results (i.e., 1/0.5=2), and a 2.times.2 pixel area in the original image is used for averaging. In another example, in reducing an image to 80% of original size, a reduction ratio of 1.25 results (i.e., 1/0.8=1.25), and a 1.25.times.1.25 pixel area in the original image is averaged.
It should be apparent from the foregoing that prior perspective projection techniques have not provided any means by which the area averaged in the original image can be controlled separately from the reduction ratio. Accordingly, prior perspective projection methods have not allowed for any control of moire suppression v. sharpness, with enhanced moire suppression provided by a larger averaging area and enhanced sharpness provided by a smaller averaging area.
Accordingly, in light of the foregoing and other deficiencies associated with prior digital image downsampling methods and apparatus, it has been deemed desirable to develop a method and apparatus for digital image reduction using an improved "extendible" perspective projection technique which allows for flexible control of the averaging cell or window size separately from the reduction ratio to improve moire suppression or sharpness as desired in the resulting reduced-size image.
Furthermore, it has been deemed desirable to provide a method and apparatus wherein the extendible perspective projection technique is implemented together with ordinary perspective projection or together with a combined one-dimensional filter and linear interpolation technique to produce a reduced-size image of a quality comparable to those produced by the prior technique of using a two-dimensional pre-filter prior to interpolation at a much lesser cost due to the reduced number of required scanline buffers.